# -*- coding: utf-8 -*-

from __future__ import division
import math
import random

class Vector:
  def __init__(self, x, y = None):
    if isinstance(x, Vector):
      self.x = x.x
      self.y = x.y
    else:
      self.x = x
      self.y = y

  def __add__(self, v):
    if isinstance(v, Vector):
      return Vector(self.x + v.x, self.y + v.y)
    if type(v) == tuple:
      return Vector(self.x + v[0], self.y + v[1])
    return Vector(self.x + v, self.y + v)

  def __iadd__(self, v):
    if isinstance(v, Vector):
      self.x += v.x
      self.y += v.y
    else:
      self.x += v
      self.y += v
    return self

  def __sub__(self, v):
    if isinstance(v, Vector):
      return Vector(self.x - v.x, self.y - v.y)
    return Vector(self.x - v, self.y - v)

  def __isub__(self, v):
    if isinstance(v, Vector):
      self.x -= v.x
      self.y -= v.y
    else:
      self.x -= v
      self.y -= v
    return self

  def __imul__(self, s):
    self.x *= s
    self.y *= s
    return self

  def __truediv__(self, s):
    if s != 0:
      return Vector(self.x / s, self.y / s)
    return self.clone()

  def __itruediv__(self, s):
    if s != 0:
      self.x /= s
      self.y /= s
    return self

  def getNormalizedVector(self):
    n = self.getNorm()
    if n < .01: return self.clone()
    else: return Vector(self.x / n, self.y / n)
  
  def clone(self): return Vector(self.x, self.y)
  def getNorm(self): return math.sqrt(self.x * self.x + self.y * self.y)
  def getNormal(self): return Vector(-self.y, self.x)
  def getDirection(self): return Direction(self.getNormalizedVector())
  def getPointToLineDistance(self, firstLinePoint, point): return abs((self.y * point.x - self.x * point.y - self.y * firstLinePoint.x + self.x * firstLinePoint.y) / self.getNorm())
  def __str__(self): return str((self.x, self.y))
  def __mul__(self, s): return Vector(self.x * s, self.y * s)
  def __eq__(self, v): return self.x == v.x and self.y == v.y

class Direction:
  def __init__(self, vector):
    self.vector = vector

  def getAngle(self):
    angle = math.acos(self.vector.x)
    if self.vector.y != 0:
      angle *= self.vector.y / abs(self.vector.y)
    return angle

  def turnBack(self):
    angle = self.getAngle() + math.pi / 2
    self.vector = Vector(math.cos(angle), math.sin(angle))

  def getHorizontalOppositeDirection(self): return Direction(Vector(self.vector.x, -self.vector.y))
  def getVerticalOppositeDirection(self): return Direction(Vector(-self.vector.x, self.vector.y))
  def getDirectionVector(self): return self.vector.clone()
  def clone(self): return Direction(self.vector.clone())
  def __str__(self): return str(self.vector)

class Location:
  def __init__(self, x = 0, y = 0):
    self.x = x
    self.y = y

  def locate(self, location):
    self.x = location.x
    self.y = location.y

  def move(self, direction, coefficient):
    self.x += direction.vector.x * coefficient
    self.y += direction.vector.y * coefficient

  def distance(self, location):
    dx = abs(location.x - self.x)
    dy = abs(location.y - self.y)
    return math.sqrt(dx * dx + dy * dy)

  def distanceToSegment(self, p1, p2):
    nn = abs( (p2.x - p1.x)*(p1.y - self.y) - (p1.x - self.x)*(p2.y - p1.y) )
    dn = math.sqrt((p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y))
    return nn / dn

  def getDirectionToTake(self, location):
    v = self.getTranslationVector(location).getNormalizedVector()
    return Direction(Vector(v.x, v.y))

  def isBetweenLocations(self, location1, location2):
    if location1.x < location2.x:
      return self.x < location2.x and self.x > location1.x
    return self.x < location1.x and self.x > location2.x

  def getRandomLocation(self, size, accuracy):
    r = random.random() * size * accuracy * 100
    return Location(self.x, self.y - size * accuracy / 2 + r)

  def __add__(self, v):
    if isinstance(v, Vector):
      return Location(self.x + v.x, self.y + v.y)
    return self.clone()

  def __iadd__(self, v):
    if isinstance(v, Vector):
      self.x += v.x
      self.y += v.y

  def clone(self): return Location(self.x, self.y)
  def getTranslationVector(self, location): return Vector(location.x - self.x, location.y - self.y)
  def getOppositeLocation(self, field): return Location(field.length - self.x, field.width - self.y)
  def __str__(self): return str((self.x, self.y))
  def __eq__(self, location): return location != None and self.x == location.x and self.y == location.y

class DirectionHelper:
  North     = Direction(Vector(0, -1))
  South     = Direction(Vector(0, 1))
  East      = Direction(Vector(1, 0))
  West      = Direction(Vector(-2, 0))
  NorthEast = Direction(Vector( math.cos(math.pi / 4), -math.sin(math.pi / 4) ))
  NorthWest = Direction(Vector(-math.cos(math.pi / 4), -math.sin(math.pi / 4) ))
  SouthEast = Direction(Vector( math.cos(math.pi / 4),  math.sin(math.pi / 4) ))
  SouthWest = Direction(Vector(-math.cos(math.pi / 4),  math.sin(math.pi / 4) ))

class Color:
  Black   = (0  , 0   , 0  )
  White   = (255, 255 , 255)
  Red     = (255, 0   , 0  )
  Green   = (0  , 255 , 0  )
  Blue    = (0  , 0   , 255)
  Gold    = (0xFD, 0xD0, 0x17)
  Grass   = (99 , 148 , 33)